package lib

import "strconv"

//link to 494 227
func init() {
	Probs = append(Probs, Problem{
		Num:         282,
		Discription: "给数字间添加+-*使得形成的表达式等于指定值",
		Level:       3,
		Labels: map[string]int{
			"递归": 1,
			"栈":  1,
		},
	})
}

func AddOperators(num string, target int) []string {
	//已计算乘法、添加减法效果后的数字栈
	s := make([]int, 0)
	res := make([]string, 0)
	var dfs func(int, byte, string)

	//start表示可以在在num[start]之后添加符号
	//前一个符号
	//当前的表达式字符串，以符号结尾，如果遍历完了以数字结尾
	dfs = func(start int, preSign byte, str string) {
		//遍历完成，计算表达式是否等于指定值
		if start == len(num) {
			num := 0
			for i := range s {
				num += s[i]
			}
			if num == target {
				res = append(res, str)
			}
			return
		}

		curNum := 0
		//留一个栈顶值，方便回溯回来时恢复s的状态
		topNum := 0
		if len(s) > 0 {
			topNum = s[len(s)-1]
		}

		//不断增加位数，遍历可能的符号添加位置
		for i := start; i < len(num); i++ {
			//除去前导0
			if i > start && curNum == 0 {
				break
			}

			//计算添加符号的位置和上一个符号之间的数字（nums[start:i+1]）
			curNum = curNum*10 + int(num[i]-'0')
			//更新数字栈
			if len(s) == 0 {
				s = append(s, curNum)
			} else {
				switch preSign {
				case '+':
					s = append(s, curNum)
				case '-':
					s = append(s, -curNum)
				case '*':
					s[len(s)-1] = s[len(s)-1] * curNum
				}
			}

			tempStr := str + strconv.Itoa(curNum)
			if i+1 == len(num) {
				//如果curNum已经到头了，无需添加后序的符号
				dfs(i+1, ' ', tempStr)
			} else {
				dfs(i+1, '+', tempStr+"+")
				dfs(i+1, '-', tempStr+"-")
				dfs(i+1, '*', tempStr+"*")
			}

			//恢复数字栈的状态
			//len(s) == 1 && preSign != '*'：第一次添加curNum
			if (len(s) == 1 && preSign != '*') || preSign == '+' || preSign == '-' {
				s = s[:len(s)-1]
			} else {
				s[len(s)-1] = topNum
			}
		}
	}

	dfs(0, ' ', "")
	return res
}
